package com.cn.codebrush.二叉树;

/**
 * @Author Boolean
 * @Date 2022/5/5 11:59
 * @Version 1.0
 */
public class No235二叉搜索树的最近公共祖先 {
    public static void main(String[] args) {
        /**
         * [6,2,8,0,4,7,9,null,null,3,5]
         * 2
         * 8
         * 输出：6
         */

        TreeNode root = new TreeNode(2);
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(3);

        root.left = a;
        root.right = b;

        System.out.println(lowestCommonAncestor(root,a,b));
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val == p.val){
            return p;
        }
        if(root.val == q.val){
            return q;
        }

        if(p.val<root.val && q.val<root.val){
            return  lowestCommonAncestor(root.left,p,q);
        }else if(p.val>root.val && q.val>root.val){
            return  lowestCommonAncestor(root.right,p,q);
        }else {
            return root;
        }
    }
}
